Bivariate polynomials associated with binary trees created by QuickSort

Abstract: In this talk we describe a generating series whose coefficients are polynomials that, for a given positive integer $n$, encode the depth at which the various list entries appear as labeled nodes in the binary trees obtained by QuickSorting permutations of the list consisting of one copy of each of the first $n$ non-negative integers. Extracting the appropriate coefficients yields information for the number of times a given list entry appears at a given depth, the total number of list entries that appear at a given depth, and consequently the average number of list entries that appear at a given depth taken over all $n!$ permutations. Joint work with David M. Bradley.

Mathematics

Audience: researchers in the topic

Combinatorial and additive number theory (CANT 2025)